package Text49;

import java.util.*;

public class Main {
    static int N = 60, n, ans;
    static int[] a = new int[N];
    static int[] up = new int[N];
    static int[] down = new int[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (true) {
            n = in.nextInt();
            if (n == 0) {
                break;
            }
            for (int i = 1; i <= n; i++) {
                a[i] = in.nextInt();
            }
            ans = n;
            dfs(1, 0, 0);
            System.out.println(ans);
        }
    }

    private static void dfs(int u, int st, int sd) {
        if (st + sd >= ans) {
            return;
        }
        if (u == n + 1) {
            ans = st + sd;
            return;
        }
        //接下来就是两种上升或者下降的情况
        //第一种情况：寻找上升子序列
        int k = 0;
        while (k < st && up[k] > a[u]) {
            k++;
        }
        int t = up[k];
        up[k] = a[u];
        if (k >= st) {
            dfs(u + 1, st + 1, sd);
        } else {
            dfs(u + 1, st, sd);
        }
        up[k] = t;
        // 第二种情况：寻找下升子序列
        k = 0;
        while (k < sd && down[k] < a[u]) {
            k++;
        }
        t = down[k];
        down[k] = a[u];
        if (k >= sd) {
            dfs(u + 1, st, sd + 1);
        } else {
            dfs(u + 1, st, sd);
        }
        down[k] = t;
    }
}
